/**
 * @ClassName Offer42
 * @Description 剑指 Offer 42. 连续子数组的最大和
 * @Author clockTown
 * @Date 2021/8/20 8:41
 * @Version 1.0
 */
class Offer42 {
}

/**
 * dp滚动数组
 */
class Offer42V0 {
    public int maxSubArray(int[] nums) {
        int res = nums[0];
        for(int i = 1; i < nums.length; i++) {
            nums[i] += Math.max(nums[i - 1], 0);
            res = Math.max(res, nums[i]);
        }
        return res;
    }
}

/**
 * 前缀和
 */
class Offer42V1 {
    public int maxSubArray(int[] nums) {
        int preSum = 0;
        int minSum = 0;
        int maxSubSum = Integer.MIN_VALUE;
        for (int num : nums) {
            preSum += num;
            maxSubSum = Math.max(maxSubSum, preSum - minSum);
            minSum = Math.min(minSum, preSum);
        }
        return maxSubSum;
    }
}

/**
 * dp数组
 */
class Offer42V2 {
    public int maxSubArray(int[] nums) {
        /**
         *  对于一个元素，只有取和不取
         *  如果取：则 dp[i] = dp[i-1] + nums[i]
         *  如果不取：则 dp[i] = nums[i]（相当于从这个元素作为子区间的新起点，重新算起）
         *  所以 dp[i] = Math.max(dp[i-1] + nums[i],nums[i])
         */
        int[] dp = new int[nums.length];
        int maxSubSum= nums[0];
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            maxSubSum = Math.max(maxSubSum, dp[i]);
        }
        return maxSubSum;
    }
}
